<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>new 21 points</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
        
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        <style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="new-21-points">new 21 points</h1>
<ul>
<li><a href="https://leetcode.com/problems/new-21-game/">https://leetcode.com/problems/new-21-game/</a></li>
</ul>
<p>Alice plays the following game, loosely based on the card game &quot;21&quot;.</p>
<pre><code><code><div>Alice starts with 0 points, and draws numbers while she has less than K points.  During each draw, she gains an integer number of points randomly from the range [1, W], where W is an integer.  
Each draw is independent and the outcomes have equal probabilities.

Alice stops drawing numbers when she gets K or more points.  What is the probability that she has N or less points?

Example 1:

Input: N = 10, K = 1, W = 10
Output: 1.00000
Explanation:  Alice gets a single card, then stops.
Example 2:

Input: N = 6, K = 1, W = 10
Output: 0.60000
Explanation:  Alice gets a single card, then stops.
In 6 out of W = 10 possibilities, she is at or below N = 6 points.
Example 3:

Input: N = 21, K = 17, W = 10
Output: 0.73278
Note:

0 &lt;= K &lt;= N &lt;= 10000
1 &lt;= W &lt;= 10000
Answers will be accepted as correct if they are within 10^-5 of the correct answer.
The judging time limit has been reduced for this question.
</div></code></code></pre>
<h1 id="solution-1">solution 1</h1>
<ul>
<li><a href="https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N)">https://leetcode.com/problems/new-21-game/discuss/132334/One-Pass-DP-O(N)</a></li>
</ul>
<p>Intuition:</p>
<pre><code>The same problems as &quot;Climbing Stairs&quot; or &quot;Fibo Sequence&quot;.
</code></pre>
<p>Explanation:</p>
<pre><code>dp[i] is the probability that we get points i at some moment.
In another word:
1 - dp[i]is the probability that we skip the points i.
</code></pre>
<p>The do equation is that:</p>
<pre><code>dp[i] = sum(last W dp values) / W

To get Wsum = sum(last W dp values),
we can maintain a sliding window with size at most W.
</code></pre>
<p>Time Complexity:</p>
<pre><code>Time O(N)
Space O(N), can be improve to O(W)
</code></pre>
<p>Java:</p>
<pre><code class="language-java"><div>    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">double</span> <span class="hljs-title">new21Game</span><span class="hljs-params">(<span class="hljs-keyword">int</span> N, <span class="hljs-keyword">int</span> K, <span class="hljs-keyword">int</span> W)</span> </span>{
        <span class="hljs-keyword">if</span> (K == <span class="hljs-number">0</span> || N &gt;= K + W) <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>;
        <span class="hljs-keyword">double</span> dp[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">double</span>[N + <span class="hljs-number">1</span>],  Wsum = <span class="hljs-number">1</span>, res = <span class="hljs-number">0</span>;
        dp[<span class="hljs-number">0</span>] = <span class="hljs-number">1</span>;
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt;= N; ++i) {
            dp[i] = Wsum / W;
            <span class="hljs-keyword">if</span> (i &lt; K) Wsum += dp[i]; <span class="hljs-keyword">else</span> res += dp[i];
            <span class="hljs-keyword">if</span> (i - W &gt;= <span class="hljs-number">0</span>) Wsum -= dp[i - W];
        }
        <span class="hljs-keyword">return</span> res;
    }
</div></code></pre>
<p>Python:</p>
<pre><code class="language-python"><div>    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">new21Game</span><span class="hljs-params">(self, N, K, W)</span>:</span>
        <span class="hljs-keyword">if</span> K == <span class="hljs-number">0</span> <span class="hljs-keyword">or</span> N &gt;= K + W: <span class="hljs-keyword">return</span> <span class="hljs-number">1</span>
        dp = [<span class="hljs-number">1.0</span>] + [<span class="hljs-number">0.0</span>] * N
        Wsum = <span class="hljs-number">1.0</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, N + <span class="hljs-number">1</span>):
            dp[i] = Wsum / W
            <span class="hljs-keyword">if</span> i &lt; K: Wsum += dp[i]
            <span class="hljs-keyword">if</span> i - W &gt;= <span class="hljs-number">0</span>: Wsum -= dp[i - W]
        <span class="hljs-keyword">return</span> sum(dp[K:])
</div></code></pre>
<h1 id="solution-2">solution 2</h1>
<p>这篇文章解释了为啥最后的结果是 sumP(K, K+W-1) , 涉及到了朴素贝叶斯定理</p>
<ul>
<li><a href="https://www.cnblogs.com/grandyang/p/10386525.html">https://www.cnblogs.com/grandyang/p/10386525.html</a></li>
</ul>
<pre><code><code><div>通常来说，我们要更新 sum[i]，那么只要知道了 sum[i-1]，就只要算出 P[i]，就行了，因为 sum[i] = sum[i-1] + P[i]。但这道题的更新其实比较复杂，要考虑两个关键的位置，K和W，我们还是用经典的21点游戏来举例说明吧，N=21, K=17, W=10。
先来说一下当点数不超过 10 的更新方法，这个其实比较简单，比如拿到七点的概率 P[7]，根据我们上面对于 P(x) 的求法，我们知道可以拆分为下列多种情况：先拿到六点的概率 (P[6]) 乘以再拿一个1点的概率 (1/W)，先拿到五点的概率 (P[5]) 乘以再拿一个2点的概率 (1/W)，...，
先拿到一点的概率 (P[1]) 乘以再拿一个六点的概率 (1/W)，直接拿个七点的概率 (1/W)，那么统统加起来，就是:

P[7] = 1/W * (P[6] + p[5] + ... + P[1] + P[0]) = 1/W * sum[6]

那么归纳一下，对于 i &lt;= W 的情况下：

P[i] = 1/W * sum[i-1]
sum[i] = sum[i-1] + P[i] = sum[i-1] + sum[i-1] / W     (when i &lt;= W)

那么当 i &gt; W 的时候，情况是不一样的，比如要求得到 15 点的概率 P[15]，那么还是根据上面求 P(x) 的方法，拆分为下面多种情况：先拿到 14 点的概率 (P[14]) 乘以再拿一个1点的概率 (1/W)，
先拿到 13 点的概率 (P[13]) 乘以再拿一个2点的概率 (1/W)，...，先拿到五点的概率 (P[5]) 乘以再拿一个 10 点的概率 (1/W)，那么统统加起来就是：

P[15] = 1/W * (P[14] + P[13] + ... + P[5]) = 1/W * (sum[14] - sum[4])

那么归纳一下，对于 i &gt; W 的情况下：

P[i] = 1/W * (sum[i-1] - sum[i-W-1])
sum[i] = sum[i-1] + P[i] = sum[i-1] + (sum[i-1] - sum[i-W-1]) / W     (when i &gt; W)

到这里，你以为就大功告成了吗？图样图森破，嘛哒得斯。还有一个K呢，更新K以内的P值，和更新大于K的P值是稍有不同的，比如当 K=17 时，我们要更新 P[15]，那么跟上面分析的一样，同时还得考虑W的情况，归纳一下：

P[i] = 1/W * sum[i-1]     (when i &lt;= K &amp;&amp; i &lt;= W)
P[i] = 1/W * (sum[i-1] - sum[i-W-1])    (when i &lt;= K &amp;&amp; i &gt; W)

但是对于大于K的值，比如 P[20] 的更新方法就有所不同了，为啥呢？这要分析 20 点是怎么得来的，由于超过了 17 点就不能再摸牌了，所以 20 点只能由下列情况组成：先拿到 16 点的概率 (P[16]) 再拿到一个4点的概率 (1/W)，
先拿到 15 点的概率 (P[15]) 再拿到一个5点的概率 (1/W)，...，先拿到 10 点的概率 (P[10]) 再拿到一个 10 点的概率 (1/W)，那么统统加起来就是：

P[20] = 1/W * (P[16] + P[15] + P[14] + ... + P[10]) = 1/W * (sum[16] - sum[9])

那么我们归纳一下，就有：

P[i] = 1/W * sum[K-1]     (when i &gt; K &amp;&amp; i &lt;= W)
P[i] = 1/W * (sum[K-1] - sum[i-W-1])    (when i &gt; K &amp;&amp; i &gt; W)

讲到这里，是不是头晕又眼花，哈哈，博主也快绕晕了，最重要的四个式子已经加粗显示了，K和W的大小关系其实是不知道的，不过我们可以把二者揉在一起，我们每次使用 i-1 和 K-1 中的较小值来算 P[i] 即可，这样就完美把K融到了W的分类情况中，
当 sum 数组计算完成之后，我们就直接按照上面的条件概率公式来算 P(&lt;=N | &gt;=K) = P(&lt;=N &amp;&amp; &gt;=K) / P(&gt;=K) = sumP(K, N) / sumP(K, K+W-1) 就行了，写的累s博主了，听个《青鸟》缓解一下吧，跟博主一起唱～阿欧伊，阿欧伊，阿弄嗖啦～

还有一点让博主惊奇的地方是，这道题的条件概率和联合概率是相同的，根据之前的条件概率公式：

P(&lt;=N | &gt;=K) = P(&lt;=N &amp;&amp; &gt;=K) / P(&gt;=K)

就是说拿到不小于K点的前提下，还能不超过N点的概率，等于拿到不小于K点且不超过N点的概率除以拿到不小于K点的概率。但是实际上这道题 P(&lt;=N | &gt;=K) = P(&lt;=N &amp;&amp; &gt;=K)，即拿到不小于K点的前提下，还能不超过N点的概率，等于拿到不小于K点且不超过N点的概率。那么就是说拿到不小于K点的概率的总是为1，想想也是阿，只有在拿到不少K点的时候才停止摸牌，这样肯定点数不少于K点阿，单独计算这个概率简直是多此一举啊，参见代码如下：

class Solution {
public:
    double new21Game(int N, int K, int W) {
        if (K == 0 || N &gt;= K + W) return 1.0;
        vector&lt;double&gt; dp(K + W);
        dp[0] = 1.0;
        for (int i = 1; i &lt; K + W; ++i) {
            dp[i] = dp[i - 1];
            if (i &lt;= W) dp[i] += dp[i - 1] / W;
            else dp[i] += (dp[i - 1] - dp[i - W - 1]) / W;
            if (i &gt; K) dp[i] -= (dp[i - 1] - dp[K - 1]) / W;
        }
        return dp[N] - dp[K - 1];
    }
};
</div></code></code></pre>
<h1 id="solution-3">solution 3</h1>
<p>结合solution 2, 再看solution 3, 就比较好理解了。</p>
<ul>
<li><a href="https://leetcode.com/problems/new-21-game/discuss/132503/My-take-on-how-to-reach-at-Solution">https://leetcode.com/problems/new-21-game/discuss/132503/My-take-on-how-to-reach-at-Solution</a></li>
</ul>
<pre><code><code><div>Firstly, observe that when Alice is done playing, her points can be in range [K, K+W-1]. She can't get past K+W because she stops playing when she is at K or more.

Now, we will see how to find the probabilities to stay in the positions in the above range and store them in p[] array.

We need to know the probabilities of all elems in range [0,K] first. From there we can calculate for elems in range (K, K+W-1]

For positions x &lt;= K,
p[x] = (p[x-1] + p[x-2] + ..... + p[x-W]) * (1/W); (Probabilities of previous possible positions to get to x, multiplied by probability of choosing an elem to get to x)

For implementation, we can keep track past values using a single variable. For each new positions, we will subtract p[x-W-1] and add p[x-1]. Look at implementation below

For positions x &gt; K,
p[x] = (p[K-1] + p[K-2] + .... + p[x - W]) * 1/W; (Since, we can't/shouldn't reach x from &gt;= K positions)


public double new21Game(int N, int K, int W) {

    if(N &gt;= K+W-1) return 1.0; // all possibilities of positions after alice stops playing are from [K, K+W-1]
    
    double p[] = new double[K+W];
    double prob = 1/(W+0.0); // single elem probability
    
    double prev = 0;
    
    p[0] = 1; // Since we start from 0, initialize it to 1
    
     //Until K
    for(int i = 1; i &lt;= K; i++) {
        prev = prev - (i-W-1 &gt;= 0 ? p[i - W -1] : 0) + p[i-1];
        p[i] = prev*prob;
    }
    
    double req = p[K];
    
    // From K+1, we don't add the p[i-1] term here as it is &gt;= K
    for(int i = K+1; i &lt;= N; i++) {
        prev = prev - (i-W-1 &gt;= 0 ? p[i - W -1] : 0);
        p[i] = prev * prob;
        req += p[i];
        //System.out.println(p[i]);
    }
    
    return req;
}
</div></code></code></pre>
<p>solution 1 和 solution 2 有个地方不太正确，</p>
<pre><code>if(N &gt;= K+W) return 1.0;
</code></pre>
<p>应该是solution 3里面的这样</p>
<pre><code>if(N &gt;= K+W-1) return 1.0;
</code></pre>
<h1 id="solution-4-我自己写的">solution 4 我自己写的</h1>
<p>读了前面3篇文章后， 我把solution 1扩展成了下面的完整版本。</p>
<pre><code><code><div>class Solution:
    def new21Game(self, N: int, K: int, W: int) -&gt; float:
        # example: N=21, K=17, W=10
        
        dp = [1] + [0] * N
        Wsum = [1] + [0] * N  # 抽一张牌能达到i的所有的概率和
        # Wsum[1] = dp[1] + dp[0]
        # Wsum[2] = dp[2] + dp[1] + dp[0]
        # Wsum[3] = dp[3] + dp[2] + dp[1] + dp[0]
        # ...
        # Wsum[10] = dp[10] + dp[9] + ... + dp[1]
        # Wsum[11] = dp[11] + dp[10] + ... + dp[2]
        # ...
        # Wsum[16] = dp[16] + dp[15] + ... + dp[7]
        # Wsum[17] = dp[16] + dp[15] + ... + dp[8]   从17开始， 就不能再抽牌了。 所以上一次的终点只能是16
        # Wsum[18] = dp[16] + dp[15] + ... + dp[9]
        # ...
        # Wsum[21] = dp[16] + dp[15] + ... + dp[13]
        # 
        # dp[i] 永远等于 Wsum[i-1]/W
        # 针对 i&gt;=17 and i&lt;=21,  最终的答案是 res = dp[17] + dp[18] + dp[19] + dp[20]
        res = 0
        
        if K==0 or N &gt;= W+K-1:  # 这种情况下可以提前返回1.0
            return 1.0
        
        
        # (1) when i &lt; K, 
        # (1.1) if i&lt; W:
        # P[i] = 1/W * sum[i-1]
        # sum[i] = sum[i-1] + P[i]
        #
        # like
        # P[7] = 1/W * (P[6] + p[5] + ... + P[1] + P[0]) = 1/W * sum[6]
        #
        # (1.2) if i &gt;= w:
        # P[i] = 1/W * sum[i-1]
        # sum[i] = sum[i-1] + P[i] - P[i-w] = 
        #
        # like:
        # P[15] = 1/W * (P[14] + P[13] + ... + P[5]) = 1/W * (sum[14] - sum[4])

        for i in range(1, K):
            dp[i] = Wsum[i-1] / W
            Wsum[i] = Wsum[i-1] + dp[i]
            if i &gt;= W:
                Wsum[i] = Wsum[i] - dp[i-W]
        
        
        # (2) when  K&lt;= i &lt;= N
        # 但是对于大于K的值，比如 P[20] 的更新方法就有所不同了，为啥呢？这要分析 20 点是怎么得来的，由于超过了 17 点就不能再摸牌了，
        # 所以 20 点只能由下列情况组成：
        #   先拿到 16 点的概率 (P[16]) 再拿到一个4点的概率 (1/W)，
        #   先拿到 15 点的概率 (P[15]) 再拿到一个5点的概率 (1/W)，
        #   ...，
        #   先拿到 10 点的概率 (P[10]) 再拿到一个 10 点的概率 (1/W)，那么统统加起来就是：
        # P[20] = 1/W * (P[16] + P[15] + P[14] + ... + P[10]) 
        #
        # 那么我们归纳一下，就有：
        # (2.1) if i &lt; w
        # P[i] = 1/W * sum[i-1]    
        # sum[i] = sum[i-1]
        #
        # (2.2) if i &gt;= w:
        # P[i] = 1/W * sum[i-1]     
        # sum[i] = sum[i-1] - p[i-w]
        #
        
        for i in range(K, N+1):
            dp[i] = Wsum[i-1] / W
            Wsum[i] = Wsum[i-1]
            res += dp[i]
            if i &gt;= W:
                Wsum[i] = Wsum[i] - dp[i-W]
        return res
</div></code></code></pre>

    </body>
    </html>